package com.yvon.service.demo.algorithm.offer;

/**
 * 二维数组中的查找
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9804.%20%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9F%A5%E6%89%BE/README
 */
public class P04 {
    public static void main(String[] args) {
        Solution solution = new P04().new Solution();
        int[][] matrix = {{1,   4,  7, 11, 15},
                          {2,   5,  8, 12, 19},
                          {3,   6,  9, 16, 22},
                          {10, 13, 14, 17, 24},
                          {18, 21, 23, 26, 30}};
        System.out.println(solution.findNumberIn2DArray(matrix, 29));
    }

    /**
     * 换一种观察角度，以右上角位置为基点，往左数值逐渐变小，往下数值逐渐变大。
     * 且该角度放在数组任意位置都成立，相当于模拟了一棵二叉搜索树（Binary Search Tree）。
     * 根据二叉搜索树特点，从右上角（或左下角）开始查找即可。
     */
    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            int m = matrix.length;
            int n = matrix[0].length;
            for (int i = m - 1, j = 0; i >= 0 && j < n;) {
                if (matrix[i][j] == target) {
                    return true;
                }
                if (matrix[i][j] < target) {
                    j ++;
                }else {
                    i --;
                }
            }
            return false;
        }
    }
}
